package 二分查找;

import java.util.Arrays;

public class LeetCode300_最长递增子序列 {
    /**
     * 状态定义：
     *        dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度
     * 转移方程：
     *        dp[i] = max(dp[i], d[j]+1) for j in [0,i)
     * 初始状态：
     *        dp[i]所有元素置1，含义是每个元素都至少可以单独成为子序列，此时长度都为1
     * 返回值：
     *        返回 dp 列表最大值，即可得到全局最长上升子序列长度
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

}
